In the encoding of an image (static or video image), a prediction encoding method is a mainstream, in which pixel values of an encoding target are predicted by means of spatial or temporal prediction using previously-decoded pixels.
For example, in 4×4 block horizontal intra prediction in H.264/AVC, a 4×4 block from pixel A to pixel P (described as “A . . . P”, similar forms will be used in other descriptions) as an encoding target is predicted horizontally using previously-decoded adjacent pixels a . . . d on the left side, as shown below:
                    a        |                            A        ->                            B        ->                            C        ->                            D        ->                                b        |                    E              F              G              H                          c        |                    I              J              K              L                          d        |                    M              N              O              P      
That is, horizontal prediction is performed as follows:    A=B=C=D=a    E=F=G=H=b    I=J=K=L=c    M=N=O=P=d
Next, the prediction residual is computed as follows:
A-aB-aC-aD-aE-bF-bG-bH-bI-cJ-cK-cL-cM-dN-dO-dP-d
After that, orthogonal transformation, quantization, and entropy encoding are executed so as to perform compressive encoding.
Similar operation is performed in motion-compensated prediction. That is, in 4×4 block motion compensation, a 4×4 block A′ . . . P′ as a result of prediction of A . . . P by using another frame is generated as follows:    A′ B′ C′ D′    E′ F′ G′ H′    I′ J′ K′ L′    M′ N′ O′ P′
Then, the prediction residual is computed as follows:
A-A′B-B′C-C′D-D′E-E′F-F′G-G′H-H′I-I′J-J′K-K′L-L′M-M′N-N′O-O′P-P′
After that, orthogonal transformation, quantization, and entropy encoding are executed so as to perform compressive encoding.
For the upper-left position (as an example) of the block, a corresponding decoder obtains a predicted value A′ and a decoded value (A-A′) of the prediction residual, and acquires an original pixel value A as the sum of the above-obtained values. This is a reversible case. However, even in an irreversible case, a decoder obtains a prediction residual decoded value (A-A′+Δ) (Δ is an encoding noise), and acquires (A+Δ) by adding a predicted value A′ to the above-obtained value.
The above explanation is applied to 16 (i.e., 4×4) pixel values. Below, a one-dimensional form based on a simplified concept will be shown. Also below, a popular 8-bit pixel value is employed. Therefore, the pixel value is an integer within a range from 0 to 255 (i.e., including 256 integers). Similar explanations can be applied to other pixel values other than the 8-bit pixel value.
Now it is assumed that x denotes a pixel value as an encoding target, and x′ denotes a predicted value thereof. Since x′ is close to x, the prediction residual (x-x′) can be within a range from −255 . . . 255, and concentrates at values in the vicinity of 0, so that the number of large absolute values is relatively small. This relationship is shown in a graph of FIG. 1.
Since the information amount of biased distribution is smaller than uniform distribution, it may be compressed after the encoding. Conventionally, a highly efficient compression is achieved using such biased distribution.
Non-Patent Document 1 relates to vector encoding which is described in embodiments of the present invention explained later, and discloses a pyramid vector quantization technique where representative vectors are regularly positioned within a space.
Non-Patent Document 2 discloses a vector quantization technique based on an LBG algorithm for optimizing representative vectors of vector quantization by means of learning, so as to irregularly arrange representative vectors in a space.    Non-Patent Document 1: T. R. Fischer, “A pyramid vector quantizer”, IEEE Trans. Inform. Theory, vol. IT-32, no. 4, pp. 568-583, July, 1986.    Non-Patent Document 2: Y. Linde, A. Buzo and R. M. Gray, “An algorithm for vector quantizer design”, IEEE Trans. on Communications, vol. com-28, no. 1, pp. 84-95, January, 1980.